package com.algorithm.code.list;

import java.util.Objects;

/**
 * @program: study
 * @className: SingleList
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2020-01-19 11:12
 * @version: v1.0
 **/
public class SingleList<T> implements BaseList<T> {

    /**
     * 头结点
     */
    private final Node<T> head = new Node<>(null, null);
    /**
     * 链表长度
     */
    private int size;

    /**
     * 链表尾指针
     */
    private Node<T> tail = head;

    public static void main(String[] args) {
        SingleList<Integer> singleList = new SingleList<>();

        for (int i = 0; i < 12; i++) {
            singleList.add(2);
        }

        singleList.printAll();
////
////        for (int i = 0; i < 20; ++i) {
////            singleList.deleteFirst(i);
////        }
//
//        singleList.reverse();
//
//        singleList.printAll();
//        System.out.println(singleList.tail.value);

//        Node<Integer> middleNode = singleList.findMiddleNode();
//        System.out.println(middleNode.value);
        System.out.println("*************************");

        singleList.delete(2);
        singleList.printAll();
    }

    /**
     * 功能描述: 判断链表为空
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/19 11:16 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/19 11:16 上午
     **/
    public boolean isEmpty() {
        return head == tail;
    }

    /**
     * 添加节点
     * 1. 采用尾插法插入
     *
     * @param value
     */
    public void add(T value) {
        Node<T> node = new Node<>(value, null);
        tail.next = node;
        tail = node;
        ++size;
    }

    /**
     * @Description: 删除所有的指定元素
     * @Param:
     * @return:
     * @Author: kukuxiahuni
     * @Date: 2020/1/23
     */
    public void delete(T value) {

        if (value == null || isEmpty()) {
            return;
        }

        Node<T> p = this.head;

        while (p.next != null) {

            if (p.next.value.equals(value)) {
                p.next = p.next.next;
                continue;
            }
            p = p.next;
        }

        


    }

    /**
     * 功能描述: 删除找到的第一个
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/19 11:21 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/19 11:21 上午
     **/
    public void deleteFirst(T value) {

        if (isEmpty()) {
            return;
        }
//        /**
//         * 1. 头结点情况
//         */
//        if (head.next.value.equals(value)) {
//            --size;
//            head.next = head.next.next;
//        }
        /**
         * 2. 尾节点情况和其他情况一致
         */
        Node<T> p = head;
        while (p.next != null) {
            /**
             * 删除
             */
            if (p.next.value.equals(value)) {
                /**
                 * 如果删除的是尾节点数据：调整tail的位置
                 */
                if (p.next == tail) {
                    tail = p;
                }
                Node<T> tmp = p.next;
                p.next = tmp.next;
                tmp = null;
                --size;

                return;
            }
            p = p.next;
        }
    }

    /**
     * 功能描述: 遍历所有节点
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/19 11:28 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/19 11:28 上午
     **/
    public void printAll() {

        Node<T> p = head.next;
        while (p != null) {
            System.out.println(p.value);
            p = p.next;
        }
    }

    /**
     * 功能描述:  @param:
     * 实现单链表的反转
     *
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/21 6:27 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/21 6:27 下午
     **/
    public void reverse() {

        if (isEmpty()) {
            return;
        }

        Node<T> cur = head.next;
        Node<T> pre = null;

        while (cur != null) {
            Node<T> next = cur.next;

            cur.next = pre;
            pre = cur;
            cur = next;
        }

        this.head.next = pre;

    }

    /**
     * @Description: 递归方式反转链表
     * 解题思路：基本上分为两个步骤
     * 1. 对节点的next及其之后的节点进行反转
     * 2. 对当前节点进行反转
     * @Param: []
     * @return: com.algorithm.code.list.BaseList.Node<T>
     * @Author: kukuxiahuni
     * @Date: 2020/1/21
     */
    public Node<T> recursiveRevise(Node<T> node) {

        if (node == null || node.next == null) {
            return node;
        }

        Node<T> p = recursiveRevise(node.next);
        node.next.next = node;
        node.next = null;

        return p;
    }

    /**
     * @Description: 查找链表的中间节点
     * @Param: []
     * @return: com.algorithm.code.list.BaseList.Node<T>
     * @Author: kukuxiahuni
     * @Date: 2020/1/22
     */
    public final Node<T> findMiddleNode() {

        Node<T> fast, slow;
        fast = slow = this.head.next;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }


}
